// https://www.lintcode.com/problem/subsets/

public class Solution {
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        if (nums.length == 0) {
            ret.add(new ArrayList<>());
        } else {
            for (int i = 0; i <= nums.length; ++i) {
                List<List<Integer>> ss = _subsets(nums, 0, i); // 从0开始，包含i个元素的子集。
                if (ss != null) {
                    for (List<Integer> subset : ss) {
                        ret.add(subset);
                    }
                }
            }
        }
        return ret;
    }
    
    protected List<List<Integer>> _subsets(int[] nums, int start, int n) {
        List<List<Integer>> ret = new ArrayList<>();
        int len = nums.length - start; // 可以提供的长度
        // 检查长度是否足够
        if ((nums.length == 0) || (len < n)) {
            return null;
        }
        if (n == 0) {
            ret.add(new ArrayList<>());
            return ret;
        }
        for (int i = start; i < nums.length; ++i) {
            List<List<Integer>> ss = _subsets(nums, i + 1, n - 1); // 凑剩下的n - 1个元
            if (ss != null) {
                if (ss.get(0).size() > 0) {
                    for (List<Integer> subset : ss) {
                        List<Integer> ns = new ArrayList<Integer>();
                        ns.add(nums[i]);
                        for (Integer si : subset) {
                            ns.add(si);
                        }
                        ret.add(ns);
                    }
                } else {
                    List<Integer> ns = new ArrayList<Integer>();
                    ns.add(nums[i]);
                    ret.add(ns);
                }
            }
        }
        return ret;
    }
}